/**
 * 
 */
package backtrack.passed;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class LetterCombinationsOfAPhoneNumber {

	/**
	Given a digit string, return all possible letter combinations that the number could represent.

	A mapping of digit to letters (just like on the telephone buttons) is given below.



	Input:Digit string "23"
	Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
	Note:
	Although the above answer is in lexicographical order, your answer could be in any order you want.
	 */

	private final static String[] map = { "", //0
			"", //1
			"abc", //2
			"def", //3
			"ghi", //4
			"jkl", //5
			"mno", //6
			"pqrs", //7
			"tuv", //8
			"wxyz" //9
	};

	public ArrayList<String> letterCombinationsIterative(String digits) {
		ArrayList<String> result = new ArrayList<String>();
		if (digits == null || digits.isEmpty()) {
			result.add("");
			return result;
		}

		ArrayList<String> list1 = new ArrayList<String>();
		ArrayList<String> list2 = new ArrayList<String>();

		for (int i = 1; i < digits.length(); i++) {
			int digit = Character.digit(digits.charAt(i), 10);
			String letters = map[digit];
			for (char letter : letters.toCharArray()) {
				if (list1.isEmpty())
					list2.add(String.valueOf(letter));
				else
					for (String str : list1) {
						list2.add(str + letter);
					}
			}
			ArrayList<String> temp = list1;
			list1 = list2;
			list2 = temp;
			list2.clear();
		}

		return list1;
	}

	public ArrayList<String> letterCombinationsIterativeQ(String digits) {
		ArrayList<String> result = new ArrayList<String>();
		if (digits == null || digits.isEmpty()) {
			result.add("");
			return result;
		}
		List<String> queue = new LinkedList<String>();
		for (char c : digits.toCharArray()) {
			int digit = Character.digit(c, 10);
			String letters = map[digit];
			int size = queue.size();
			for (char letter : letters.toCharArray()) {
				if (size == 0) {
					queue.add(String.valueOf(letter));
				} else {
					for (int i = 0; i < size; i++) {
						queue.add(queue.get(i) + letter);
					}
				}
			}
			for (int i = 0; i < size; i++) {
				queue.remove(0);
			}
		}
		for (String word : queue) {
			result.add(word);
		}

		return result;
	}

	public ArrayList<String> letterCombinations(String digits) {
		ArrayList<String> result = new ArrayList<String>();
		if (digits == null || digits.isEmpty()) {
			result.add("");
			return result;
		}
		letterCobinationsHelp(digits, 0, new StringBuilder(), result);
		return result;
	}

	private void letterCobinationsHelp(String digits, int index,
			StringBuilder cache, ArrayList<String> result) {
		if (index == digits.length()) {
			result.add(cache.toString());
		} else {
			int digit = Character.digit(digits.charAt(index), 10);
			String letters = map[digit];
			for (int i = 0; i < letters.length(); i++) {
				cache.append(letters.charAt(i));
				letterCobinationsHelp(digits, index + 1, cache, result);
				cache.setLength(cache.length() - 1);
			}
		}
	}

	public void pirtMatchWrodsIterative(int[] number) {
		assert (number.length > 0);

		int[] answer = new int[number.length];
		int index = 0; // current position of the number
		while (index >= 0) {
			for (int i = 0; i < number.length; ++i) {
				System.out.printf("%c", map[number[i]].charAt(answer[i]));
			}
			System.out.println();

			index = number.length - 1;
			while (index >= 0) {
				if (answer[index] < map[number[index]].length() - 1) {
					answer[index]++;
					break;
				} else {
					answer[index] = 0;
					index--;
				}
			}
		}
	}

	/**
	 * 
	 */
	public LetterCombinationsOfAPhoneNumber() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LetterCombinationsOfAPhoneNumber lcapn = new LetterCombinationsOfAPhoneNumber();
		String digits = "32";
		ArrayList<String> words = lcapn.letterCombinationsIterative(digits);
		for (String word : words) {
			System.out.printf("%s,", word);
		}

	}
}
